/*
题目：范围内最接近的两个素数
给你两个正整数 left 和 right ，请你找到两个整数 num1 和 num2 ，它们满足：

    left <= nums1 < nums2 <= right  。
    nums1 和 nums2 都是 质数 。
    nums2 - nums1 是满足上述条件的质数对中的 最小值 。

请你返回正整数数组 ans = [nums1, nums2] 。如果有多个整数对满足上述条件，请你返回 nums1 最小的质数对。如果不存在符合题意的质数对，请你返回 [-1, -1] 。

如果一个整数大于 1 ，且只能被 1 和它自己整除，那么它是一个质数。
https://leetcode.cn/problems/closest-prime-numbers-in-range/description/
 */
public class ClosestPrimes {
    // 核心思路：找到所有范围内的素数，然后暴力判断范围内最接近的两个质数
    private static final int INF = (int) (1e6) + 1;
    private boolean[] isPrime = null; // 是否是素数，默认是 false
    private List<Integer> primes = null; // 存储素数

    { // 动态代码块
        primes = new ArrayList<> ();
        isPrime = new boolean[INF];
        // 开始寻找所有素数 ---⭐⭐⭐⭐⭐---
        for (int i = 2; i < INF; i ++) {
            if (!isPrime[i]) {  // 如果是素数的话
                primes.add(i); // 直接添加
                // 该数的倍数都不是素数
                // 这是为了防止溢出的写法，实际上 j 是从 i^2 开始的，因为 i * (<i的因子) 都是被取消了的
                for (int j = i; j < INF / i; j ++) {
                    isPrime[j * i] = true;
                }
            }
        }
    }

    public int[] closestPrimes(int left, int right) {
        // 然后找到第一个大于等于 left 的素数
        int idx = binarySearch(left);
        int p = -1, q = -1;
        while (idx < primes.size() - 1 && primes.get(idx + 1) <= right) {
            if (p < 0 || primes.get(idx + 1) - primes.get(idx) < q - p) { // 第一次遇到或者遇到了更符合题意的答案
                p = primes.get(idx);
                q = primes.get(idx + 1);
            }
            idx ++;
        }
        return new int[] {p, q};
    }

    private int binarySearch(int num) {
        int left = 0, right = primes.size() - 1;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (primes.get(mid) >= num) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return right + 1;
    }
}
